/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const res = [];
  // 使用回溯即可，判断选左还是选右
  function dfs(Lres, Rres, index, str) {
    if (index === 2 * n) {
      res.push(str);
      return;
    }

    if (Rres === Lres) {
      dfs(Lres - 1, Rres, index + 1, str + "(");
      return;
    } else if (Lres == 0) {
      dfs(Lres, Rres - 1, index + 1, str + ")");
      return;
    } else {
      dfs(Lres - 1, Rres, index + 1, str + "(");
      dfs(Lres, Rres - 1, index + 1, str + ")");
    }
  }

  dfs(n, n, 0, "");
  return res;
};
